package puzzle.projecteuler.p100;

public class Problem094C {

	/**
	 * case 1: x, x, x+1
	 * P = 3x+1
	 * S = (x+1)/4 * sqrt((3x+1)*(x-1))
	 * So:
	 *     (3x+1)*(x-1) = y^2 
	 * <=> B^2 - 3*A^2 = 4, B=3x-1 
	 * <=> B=3x-1=2b, A=2a, b^2 - 3*a^2 = 1 
	 * 
	 * 
	 * case 2: x, x, x-1
	 * P = 3x-1
	 * S = (x+1)/4 * sqrt((3x-1)*(x+1))
	 * So:
	 *     (3x-1)*(x+1) = y^2 
	 * <=> B^2 - 3*A^2 = 4, B=3x+1 
	 * <=> B=3x+1=2b, A=2a, b^2 - 3*a^2 = 1
	 *
	 * Pell:
	 *    b + a*sqrt(3) = [2+sqrt(3)]^n
	 * => b_n = 2b_(n-1) + 3a_(n-1)
	 *    a_n =  b_(n-1) + 2a_(n-1) 
	 * @param args
	 */
	public static void main(String[] args) {
		
		long a = 1;
		long b = 2;
		long s = 0;
		long p = 0;
		do {
			long tmp = b;
			b = 2*b + 3*a;
			a = tmp + 2*a;
			
			long x = 0;
			if (2*b % 3 == 2) {//case 1
				p = 2*b+2;
				x = (2*b+1)/3;
				System.out.println("case1:\t" + x+","+x+","+(x+1)+";" + p +"," + ((x+1)*(long)Math.sqrt((3*x+1)*(x-1))/4));
			} else if (2*b%3 == 1) {//case 2
				p = 2*b-2;
				x = (2*b-1)/3;
				System.out.println("case2:\t" + x+","+x+","+(x-1)+";" + p + "," + ((x+1)*(long)Math.sqrt((3*x-1)*(x+1))/4));
			}
			s += p;
		} while (p < 1000000000);
		
		System.out.println(s);
	}
}
